/*-------------------------------------------------------------------------
 *
 * regprefix.c
 *	  提取编译后的正则表达式中的公共前缀（如果有的话）。
 *
 *
 * Portions Copyright (c) 2012-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1998, 1999 Henry Spencer
 *
 * IDENTIFICATION
 *	  src/backend/regex/regprefix.c
 *
 *-------------------------------------------------------------------------
 */

#include "regex/regguts.h"


/*
 * 前向声明
 */
static int	fc_findprefix(struct cnfa *fc_cnfa, struct colormap *fc_cm,
					   chr *fc_string, size_t *fc_slength);


/*
 * pg_regprefix - 获取正则表达式的公共前缀
 *
 * 返回以下之一：
 *	REG_NOMATCH：没有匹配正则表达式的字符串的公共前缀
 *	REG_PREFIX：有公共前缀的字符串匹配正则表达式
 *	REG_EXACT：所有满足正则表达式的字符串必须匹配相同的字符串
 *	或一个REG_XXX错误代码
 *
 * 在非失败情况下，*string被设置为包含
 * 公共前缀或准确值的malloc'd字符串，长度为*slength（以字符为单位
 * 而不是以字节为单位测量！）。
 *
 * 此函数并未完全分析所有复杂情况（例如环视
 * 约束）。因此，报告的前缀或确切匹配字符串的某些匹配字符串
 * 可能不满足正则表达式。但满足正则表达式的字符串
 * 不可能不匹配报告的前缀或确切匹配字符串。
 */
int pg_regprefix(regex_t *fc_re,
			 chr **fc_string,
			 size_t *fc_slength)
{
	struct guts *fc_g;
	struct cnfa *fc_cnfa;
	int			fc_st;

	/* 运行检查 */
	if (fc_string == NULL || fc_slength == NULL)
		return REG_INVARG;
	*fc_string = NULL;				/* 初始化用于失败的情况 */
	*fc_slength = 0;
	if (fc_re == NULL || fc_re->re_magic != REMAGIC)
		return REG_INVARG;
	if (fc_re->re_csize != sizeof(chr))
		return REG_MIXED;

	/* 初始化区域相关支持 */
	pg_set_regex_collation(fc_re->re_collation);

	/* setup */
	fc_g = (struct guts *) fc_re->re_guts;
	if (fc_g->info & REG_UIMPOSSIBLE)
		return REG_NOMATCH;

	
/*
	 * 这个实现仅考虑顶层正则表达式树节点的搜索 NFA。
	 * 因此，像回溯引用这样的约束并未完全应用，这在函数的 API 规范中是允许的。
	 */
	assert(fc_g->tree != NULL);
	fc_cnfa = &fc_g->tree->cnfa;

	/* matchall NFAs 永远没有固定的前缀 */
	if (fc_cnfa->flags & MATCHALL)
		return REG_NOMATCH;

	/*
	 * 因为一个正确的 NFA 应该永远不包含任何无出口循环，
	 * 所以我们的遍历不应该返回到之前访问过的 NFA 状态。
	 * 因此，输出字符串中最多需要 nstates 个字符。
	 */
	*fc_string = (chr *) MALLOC(fc_cnfa->nstates * sizeof(chr));
	if (*fc_string == NULL)
		return REG_ESPACE;

	/* do it */
	fc_st = fc_findprefix(fc_cnfa, &fc_g->cmap, *fc_string, fc_slength);

	assert(*fc_slength <= fc_cnfa->nstates);

	/* 清理 */
	if (fc_st != REG_PREFIX && fc_st != REG_EXACT)
	{
		FREE(*fc_string);
		*fc_string = NULL;
		*fc_slength = 0;
	}

	return fc_st;
}


/*
 * findprefix - 从cNFA中提取公共前缀
 *
 * 结果返回到预分配的chr数组string[]中，*slength（必须预设为零）对每个chr递增。
 */
static int						/* regprefix返回代码 */
fc_findprefix(struct cnfa *fc_cnfa,
		   struct colormap *fc_cm,
		   chr *fc_string,
		   size_t *fc_slength)
{
	int			fc_st;
	int			fc_nextst;
	color		fc_thiscolor;
	chr			fc_c;
	struct carc *fc_ca;

	/*
	 * “pre”状态必须只有BOS/BOL出弧，否则模式不被左锚定。
	 * 如果我们同时拥有BOS和BOL，它们必须指向同一个下一状态。
	 */
	fc_st = fc_cnfa->pre;
	fc_nextst = -1;
	for (fc_ca = fc_cnfa->states[fc_st]; fc_ca->co != COLORLESS; fc_ca++)
	{
		if (fc_ca->co == fc_cnfa->bos[0] || fc_ca->co == fc_cnfa->bos[1])
		{
			if (fc_nextst == -1)
				fc_nextst = fc_ca->to;
			else if (fc_nextst != fc_ca->to)
				return REG_NOMATCH;
		}
		else
			return REG_NOMATCH;
	}
	if (fc_nextst == -1)
		return REG_NOMATCH;

	/*
	 * 扫描连续状态，一旦找到具有多个可接受转换字符的状态即停止
	 * （要么在出弧上有多个颜色，要么是颜色具有多个成员chr）。
	 *
	 * 我们可能会找到一个具有多个出弧且都标记为相同单一颜色的状态；
	 * 这来自于像“^ab(cde|cxy)”这样的模式。在这种情况下，我们将
	 * chr“c”添加到输出字符串中，但随后在nextst == -1时退出循环。
	 * 这会留下一些未处理的情况：如果模式像“^ab(cde|cdy)”，
	 * 我们不会注意到“d”可以被添加到前缀中。但是追踪多个平行状态链
	 * 似乎并不值得。
	 */
	do
	{
		fc_st = fc_nextst;
		fc_nextst = -1;
		fc_thiscolor = COLORLESS;
		for (fc_ca = fc_cnfa->states[fc_st]; fc_ca->co != COLORLESS; fc_ca++)
		{
			/* 我们可以忽略BOS/BOL弧 */
			if (fc_ca->co == fc_cnfa->bos[0] || fc_ca->co == fc_cnfa->bos[1])
				continue;

			/*
			 * ... 但EOS/EOL弧终止搜索，以及RAINBOW弧和LACON
			 */
			if (fc_ca->co == fc_cnfa->eos[0] || fc_ca->co == fc_cnfa->eos[1] ||
				fc_ca->co == RAINBOW || fc_ca->co >= fc_cnfa->ncolors)
			{
				fc_thiscolor = COLORLESS;
				break;
			}
			if (fc_thiscolor == COLORLESS)
			{
				/* 第一个普通出弧 */
				fc_thiscolor = fc_ca->co;
				fc_nextst = fc_ca->to;
			}
			else if (fc_thiscolor == fc_ca->co)
			{
				/* 同色的另一个普通出弧 */
				fc_nextst = -1;
			}
			else
			{
				/* 超过一个普通出弧颜色终止搜索 */
				fc_thiscolor = COLORLESS;
				break;
			}
		}
		/* 如果我们没有在普通出弧上找到确切的一个颜色，则完成 */
		if (fc_thiscolor == COLORLESS)
			break;
		/* 该颜色必须是单一成员 */
		if (fc_cm->cd[fc_thiscolor].nschrs != 1)
			break;
		/* 不得有任何高颜色映射条目 */
		if (fc_cm->cd[fc_thiscolor].nuchrs != 0)
			break;

		/*
		 * 确定颜色的唯一成员chr并将其添加到前缀字符串中。
		 * 通常，colormap数据结构未提供查找颜色成员chr的方法，
		 * 除非对每个可能的chr值尝试GETCOLOR()，这完全不行。
		 * 然而，对于我们关心的情况，测试“firstchr”值
		 * 即是添加到颜色的第一个chr，应该就足够了。
		 * 有一些情况可能不再是颜色的成员（因此我们确实需要测试），
		 * 但这些情况不太可能出现在属于公共前缀的字符上。
		 * 如果我们确实遇到这样的边缘情况，我们只是退出而不
		 * 向前缀字符串添加任何内容。
		 */
		fc_c = fc_cm->cd[fc_thiscolor].firstchr;
		if (GETCOLOR(fc_cm, fc_c) != fc_thiscolor)
			break;

		fc_string[(*fc_slength)++] = fc_c;

		/* 先进到下一个状态，但只有在我们有唯一下一个状态时 */
	} while (fc_nextst != -1);

	/*
	 * 如果我们结束在只有EOS/EOL出弧指向“post”状态的状态，
	 * 那么我们有一个精确匹配字符串。注意，即使字符串的长度为零，
	 * 这也是正确的。
	 */
	fc_nextst = -1;
	for (fc_ca = fc_cnfa->states[fc_st]; fc_ca->co != COLORLESS; fc_ca++)
	{
		if (fc_ca->co == fc_cnfa->eos[0] || fc_ca->co == fc_cnfa->eos[1])
		{
			if (fc_nextst == -1)
				fc_nextst = fc_ca->to;
			else if (fc_nextst != fc_ca->to)
			{
				fc_nextst = -1;
				break;
			}
		}
		else
		{
			fc_nextst = -1;
			break;
		}
	}
	if (fc_nextst == fc_cnfa->post)
		return REG_EXACT;

	/*
	 * 否则，如果我们无法识别任何前缀字符，则返回NOMATCH ---
	 * 模式是左锚定的，但并未指定任何特定的第一个字符。
	 */
	if (*fc_slength > 0)
		return REG_PREFIX;

	return REG_NOMATCH;
}
